class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        maxlen = 0
        maxstr = ''
        for i in range(n):
            #按照奇数类的回文找一次
            cur = s[i]
            l = i - 1    
            r = i + 1
            while l >= 0 and r < n:
                if s[l] == s[r]:
                    cur = s[l] + cur + s[r]
                else:
                    break
                l -= 1
                r += 1

            #按照偶数类的回文找一次
            cur_m = ''
            l = i  
            r = i + 1
            while l >= 0 and r < n:
                if s[l] == s[r]:
                    cur_m = s[l] + cur_m + s[r]
                else:
                    break
                l -= 1
                r += 1
            curMax = cur if len(cur) > len(cur_m) else cur_m
            if len(curMax) > maxlen:
                maxlen = len(curMax)
                maxstr = curMax
        return maxstr
    
    def longestPalindromeDP(self, s: str) -> str:
        n = len(s)
        maxlen = 0
        maxstr = ''
        dp = [[ False for _ in range(n)] for _ in range(n)]
        print("没实现\n")
        pass 



if __name__ == '__main__':
    print("最长回文子串\n");

    print("中心扩散法\n")
    maxstr = Solution().longestPalindrome("babadab")
    print(maxstr) 
    maxstr = Solution().longestPalindrome("aabb")
    print(maxstr) 
    maxstr = Solution().longestPalindrome("ccc") 
    print(maxstr)

    print("\n\n动态规划法\n") 
    maxstr =  Solution().longestPalindromeDP("babadab")
    print(maxstr) 
    maxstr = Solution().longestPalindromeDP("aabb") 
    print(maxstr) 
    maxstr = Solution().longestPalindromeDP("ccc") 
    print(maxstr)